package find.duplicate.subtrees;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @Time 2019/12/31
 * @author 王光浩
 * @Need 给出一个棵二叉树，找出二叉树上所有具有相同结构，且每一个节点值对应相等的子树，结果只需返回一个具有
 *       这种相同结构子树的根节点。
 * @Thinking 使用HashMap,采用后序遍历。方法与上一次的类似，不过稍有改进。
 *           改进为：自低向上来将节点加入到HashMap中，使用两个HashMap，第一个key唯一标识符，value为是否
 *                   加入过集合中；第二个key为TreeNode，value为该TreeNode的唯一标识符；对于唯一标识符更改如下
 *                   如果一个节点的左子节点或右子节点为null，则将null加入到标识符中。
 *           复杂度分析：时间复杂度O（n），空间复杂度（n）。缺点为越向上每一个节点所需要的空间越大。
 *           
 */
public class MyMethodTwo {
	HashMap<String,Boolean> identify;
	HashMap<TreeNode,String> findIdentify;
	List<TreeNode> result;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    	identify=new HashMap<String,Boolean>();
    	findIdentify=new HashMap<TreeNode,String>();
    	result=new LinkedList<TreeNode>();
    	if(root!=null)
    	 latterTraversal(root);
    	return result;
    }
	
	/**计算根节点的唯一标识*/
    private String calucate(TreeNode node) {
    	StringBuilder tem=new StringBuilder();
    	String left;
    	String right;
    	//前序遍历值+前序遍历值，形成唯一的标识符，将NULL代替空节点
    	if(node.left==null && node.right==null){
    		left="n";
    		right="n";
    	}
    	else if(node.left==null){
    		left="n";
    		right=findIdentify.get(node.right);
    	}
    	else if(node.right==null) {
    		left=findIdentify.get(node.left);
    		right="n";
        }
    	else {
    		left=findIdentify.get(node.left);
    		right=findIdentify.get(node.right);
    	}
    	return tem.append(left).append("l").append(node.val).append("r").append(right).toString();
    }
    
    /**使用递归方法来完成对二叉树的后序遍历*/
    private void latterTraversal(TreeNode node) {
    	if(node.left!=null)
    		latterTraversal(node.left);
    	if(node.right!=null)
    		latterTraversal(node.right);
    	String key=calucate(node);    //获取唯一标识
    	//相同标识符的节点，加入结果集中，并设置为已经入过结果集
    	if(identify.containsKey(key)) {
    		if(!identify.get(key)) {
    			result.add(node);
    			identify.put(key, true);          //更新值为0
    		}
    	}
    	else {
    		identify.put(key,false);
    	}
    	findIdentify.put(node, key);    	
    }
}
